# -*- coding: utf-8 -*-

'''
Created on 11-07-05

@author: peterd
'''
import os, pickle
from datetime import datetime, date
from collections import deque
import operator
from inspect import stack


import networkx as nx
from networkx.exception import NetworkXNoPath


from django.core.exceptions import ObjectDoesNotExist
from django.utils.encoding import smart_str, smart_unicode


from infra.util.geoutil import LatLng
from mhd.models import *
from mhd.locator import MHD_StopLocator
from mhd.exceptions import *


MAX_ALLOWED_CONNECTION_DURATION_MIN = 60
MAX_ALLOWED_NUM_XFER = 6
MAX_NUM_CONNECTIONS = 60
    
class Connection:
    def __init__(self):
        self.routes_ = []
        self.duration_ = 0
        self.startStop_ = None
        self.endStop_ = None
        

    def addRoute(self, route):
        self.routes_.append(route)
        
        
    def getRoutes(self):
        return self.routes_
        
        
    def setDuration(self, duration):
        self.duration_ = duration
        
        
    def getDuration(self):
        return self.duration_


    def setStartStop(self, startStop):
        self.startStop_ = startStop
        
        
    def getStartStopName(self):
        return self.startStop_.name


    def setEndStop(self, endStop):
        self.endStop_ = endStop
        
        
    def getEndStopName(self):
        return self.endStop_.name

    
    def getPath(self):
        path = []
        for route in self.routes_:
            path.append(route.getLinkName())
        return path
            

    def dump(self):
        for route in self.routes_:
            if not route.isWalking():
                print u'%s: %s %s -> %s %s\t%d zastavky, %d min' % (route.getLinkName(),
                                                                    route.getFirstStopArrival(), 
                                                                    route.getFirstStop()['name'].encode('utf-8'),
                                                                    route.getLastStopArrival(), 
                                                                    route.getLastStop()['name'].encode('utf-8'),
                                                                    route.getNumStops(), 
                                                                    route.getDuration()
                                                                    )
            else:
                print u'%s: %s -> %s\t%d min' % (route.getLinkName(), 
                                                 route.getFirstStop()['name'].encode('utf-8'),
                                                 route.getLastStop()['name'].encode('utf-8'), 
                                                 route.getDuration()
                                                )


    def __str__(self):
        conn_details = ''        
        for route in self.routes_:
            if not conn_details:
                conn_details = '%s: %s -> %s' % (route.getLinkName(), route.getFirstStop()['id'], route.getLastStop()['id'])
            else:
                conn_details = '%s\n%s: %s -> %s' % (conn_details, route.getLinkName(), route.getFirstStop()['id'], route.getLastStop()['id'])
        return conn_details        

    
    def __unicode__(self):        
        conn_details = ''        
        for route in self.routes_:
            if not conn_details:
                conn_details = u'%s: %s %s -> %s %s\t%d zastavky, %d min' % (route.getLinkName(),
                                                                    route.getFirstStopArrival(), 
                                                                    route.getFirstStop()['name'].encode('utf-8'),
                                                                    route.getLastStopArrival(), 
                                                                    route.getLastStop()['name'].encode('utf-8'),
                                                                    route.getNumStops(), 
                                                                    route.getDuration()
                                                                    )
            else:
                conn_details = u'%s\n%s: %s %s -> %s %s\t%d zastavky, %d min' % (conn_details, route.getLinkName(),
                                                                    route.getFirstStopArrival(), 
                                                                    route.getFirstStop()['name'].encode('utf-8'),
                                                                    route.getLastStopArrival(), 
                                                                    route.getLastStop()['name'].encode('utf-8'),
                                                                    route.getNumStops(), 
                                                                    route.getDuration()
                                                                    )                
        return conn_details        
        

# REFACTOR: should be further derived to WalkingRoute, DrivingRoute
class Route:
    def __init__(self, linkName, linkDirection, stops, duration):
        if linkName[0] == 'w':
            self.link_ = 'w'
            self.linkName_ = 'w'
        else:
            try:
                self.link_ = MHD_Link.objects.get(name = linkName)
                self.linkName_ = self.link_.name            
            except ObjectDoesNotExist:
                raise NoSuchLink
        self.linkDirection_ = linkDirection
        self.stops_ = stops
        self.duration_ = duration
        self.arrival_ = None
        
    
    def isWalking(self):
        return not isinstance(self.link_, MHD_Link)    
            
        
    def getDuration(self):
        return self.duration_
        
        
    def setFirstStopArrival(self, arrival):
        self.arrival_ = arrival 


    def getFirstStopArrival(self):
        return self.arrival_ 
        

    def getLastStopArrival(self):
        rv = None
        if self.arrival_ and self.duration_:
            rv = datetime.datetime(1, 1, 1, self.arrival_.hour, self.arrival_.minute) + datetime.timedelta(minutes = self.duration_)
        return rv

        
    def addStop(self, id, stop):
        self.stops_.append((id, stop))


    def getLink(self):     
        return self.link_
    
    
    def getLinkDirection(self):
        return self.linkDirection_
        

    def getNumStops(self, startWith = None):
        return len(self.stops_)

    
    def getFirstStop(self):
        rv = None
        if len(self.stops_) > 0:
            rv = self.stops_[0]
        return rv


    def getLastStop(self):
        rv = None
        if len(self.stops_) > 0:
            rv = self.stops_[len(self.stops_) - 1]
        return rv


    def getLastStopId(self):
        rv = None
        if len(self.stops_) > 0:
            rv = self.stops_[len(self.stops_) - 1]['id']
        return rv


    def getLinkName(self):
        return self.linkName_
        
    def __str__(self):        
        return "link: %s, direction: %s, firstStop: %s, lastStop: %s" % (self.linkName_, self.direction_.direction, self.firstStop_, self.lastStop_)        

    
    def __unicode__(self):        
        return u"link: %s, direction: %s, firstStop: %s, lastStop: %s" % (self.linkName_, self.direction_.direction, self.firstStop_, self.lastStop_)        
    


# returns 'wrk_days_school' | 'wrk_days_noschool' | 'weekend'  corresponding to the departure date 
def departure_to_timetable_label(departure):
    # first check whether departure date is weekend or a public hol
    timetable_label = 'wrk_days_school' 
    
    try:
        MHD_Public_Holiday.objects.get(start_date__lte = departure, end_date__gte = departure)
        timetable_label = 'weekend'
    except ObjectDoesNotExist:
        if date.weekday(departure) in [5, 6]:
            timetable_label = 'weekend'
        else:
            try:        
                MHD_School_Holiday.objects.get(start_date__lte = departure, end_date__gte = departure)
                timetable_label = 'wrk_days_noschool'
            except ObjectDoesNotExist:
                timetable_label = 'wrk_days_school'            
    return timetable_label


class NoSuchRoute:
    pass


def linkRoute(link, startNode, graph, timetable_label):
    endRoute = False
    duration = 0
    node = startNode
    #stopNum = 1
    while not endRoute:
        linkEdge = False
        for edge in graph.getEdges(node, timetable_label):
            if edge[2] == link and edge[3]['type'] == 'd':
                stop = graph.getStop(edge[0], timetable_label)
                yield (stop, duration)
                #stopNum = stopNum + 1
                duration = duration + edge[3]['weight']                            
                node = edge[1]
                linkEdge = True
                
                nextStop = graph.getStop(node, timetable_label)
                for l in nextStop['links']:
                    if l['name'] == link:
                        if l['last']:
                            #direction = l['dir']
                            endRoute = True                            
                            break
                            
                break
            
        if not linkEdge:
            endRoute = True
    yield (graph.getStop(node, timetable_label), duration)



def dumpConnections(a, b, connections, departure):
    if connections:
        i = 1
        print "a: %d -> b: %d, departure: %s" % (a, b, departure)
        for connection in connections:
            print 'Connection %d (%d min):\n%s\n' % (i, connection.getDuration(), connection)
            i = i + 1
    

class MHD_Context():
    def __init__(self, startStop, endStop, max_num_xfer, max_num_walking, max_num_connections, startStopLinks, endStopLinks):
        self.startStop_ = startStop
        self.endStop_ = endStop
        self.curStop_ = startStop
        self.num_xfer_ = max_num_xfer
        self.max_num_xfer_ = max_num_xfer
        self.num_walking_ = max_num_walking
        self.max_num_walking_ = max_num_walking
        self.num_connections_ = 0
        self.max_num_connections_ = max_num_connections
        self.startStopLinks_ = startStopLinks
        self.endStopLinks_ = endStopLinks   
        self.seen_links_ = []
        self.seen_links_stops_ = []
        self.link_stops_ = {}
        self.link_stops_all_ = {}
        self.connections_ = {}
        self.seen_link_list_ = [] 
        self.completed_routes_ = {}
        self.path_completed_ = False
        self.conn_path_ = []
        self.seen_conn_paths_ = []
        
        
    def reset(self):
        del self.seen_links_[:]
        self.link_stops_.clear()
        
            
    def traverse(self, link):
        global traverse_level
        traverse_level = traverse_level + 1
        #print "traverse level: %d" % traverse_level
        if self.linkInStartStopLinks(link):
            self.path_completed_ = True
            return self.conn_path_
        #for prev_link in self.link_stops_[link[:2]]:
        try:
            for prev_link in self.link_stops_[link]:            
                if prev_link != 'w':
                    if traverse_level == 10:
                        pass
                    self.traverse(prev_link)
                    if self.path_completed_:
                        self.conn_path_.append(prev_link)
                        break
        except KeyError:
            pass
        
        return self.conn_path_
        

        
    def linkInEndStopLinks(self, link):
        rv = False
        for end_stop_link in self.endStopLinks_:
            # compare link_name, direction_id tuples
            if (link[0], link[1]) == (end_stop_link[0], end_stop_link[1]):
                rv = True
                break
        return rv
          

    def linkInStartStopLinks(self, link):
        rv = False
        for start_stop_link in self.startStopLinks_:
            # compare link_name, direction_id tuples
            if (link[0], link[1]) == (start_stop_link[0], start_stop_link[1]):
                rv = True
                break
        return rv

        
    def addToCompletedRoutes(self, link, direction_id):
        if self.completed_routes_.has_key(link):
            if not direction_id in self.completed_routes_[link]:
                self.completed_routes_[link].append(direction_id)
        else:
            self.completed_routes_[link] = [direction_id]


    def removeLinkWhenCompleted(self, links, stop):
        to_be_removed_links = []
        for link in links:
            if self.completed_routes_.has_key(link):
                for l in stop['links']:
                    if l['name'] == link and l['dir'] in self.completed_routes_[link]:
                        to_be_removed_links.append(link)
                        break
        return list(set(links) - set(to_be_removed_links))
    
    
    
        
    def gotMaxNumConnections(self):
        return self.num_connections_ == self.max_num_connections_ 
        
    
    def getMaxNumXfer(self):
        return self.max_num_xfer_

    def getCurrentStop(self):
        return self.curStop_


    def setCurrentStop(self, curStop):
        self.curStop_ = curStop

    
    def getNumWalking(self):
        return self.num_walking_


    def setNumWalking(self, numWalking):
        if numWalking > self.max_num_walking_:
            self.num_walking_ = self.max_num_walking_
        else:
            self.num_walking_ = numWalking
            
            
    def getStops(self, link):
        rv = []
        if self.link_stops_all_.has_key(link):
            rv = self.link_stops_all_[link]
        return rv

        
    def getStartStop(self):
        return self.startStop_
    

    def getEndStop(self):
        return self.endStop_
    
    
    def getStartStopLinks(self):
        return self.startStopLinks_


    def getEndStopLinks(self):
        return self.endStopLinks_
    
    
    def seenLink(self, link):
        return link in self.seen_links_ 
 

    def getSeenLinks(self):
        return self.seen_links_
    
    
    def seenStop(self, link, stop_id):
        rv = False
        if self.link_stops_all_.has_key(link):
            rv = stop_id in self.link_stops_all_[link] 
        return rv

   
    def addLinkStop(self, xfer_link, cur_link, stop_num):
        if self.link_stops_.has_key(xfer_link):
            self.link_stops_[xfer_link].append((cur_link[0], cur_link[1], stop_num))
        else:
            self.link_stops_[xfer_link] = [(cur_link[0], cur_link[1], stop_num)]


    def addLinkStop__old(self, xfer_link, cur_link, stop_num):
        if self.link_stops_.has_key(xfer_link[:2]):
            self.link_stops_[xfer_link[:2]].append((cur_link[0], cur_link[1], stop_num))
        else:
            self.link_stops_[xfer_link[:2]] = [(cur_link[0], cur_link[1], stop_num)]




    def addToSeenLinks(self, link):
        self.seen_links_.append(link)


    def removeFromSeenLinks(self, link):
        i = 0
        for l in self.seen_links_:
            if l == link:
                self.seen_links_.pop(i)
                try:
                    del self.link_stops_[link]
                except KeyError:
                    pass
                break
            i = i + 1


    def getNumXfer(self):
        return self.num_xfer_


    def setNumXfer(self, num_xfer):
        if num_xfer > self.max_num_xfer_:
            self.num_xfer_ =  self.max_num_xfer_
        else:
            self.num_xfer_ =  num_xfer

        
    def onEndStop(self, link, mhd_graph, timetable_label):
        conn_path = []
        for frame in stack():
            if frame[3] == 'search':
                cur_link = frame[0].f_locals['cur_link']
                stop_num = frame[0].f_locals['stop_num']
                if stop_num:
                    conn_path.append((cur_link[0], cur_link[1], stop_num))
                else:
                    conn_path.append(cur_link)
        conn_path.reverse()
        
        print conn_path
                                     
        if conn_path == [(u'21', 53, 14), (u'8', 12, 10)]:
            pass
        
        #self.seen_conn_paths_.append(self.conn_path_[:])

        connection = Connection()
        conn_duration = 0
        first_stop_id = None
        last_stop_id = None
        
        for link in conn_path:
            # first link
            if link == conn_path[0]:
                first_stop_id = self.startStop_
                if link == conn_path[-1]:
                    last_stop_id = self.endStop_
                else:
                    last_stop_id = mhd_graph.getStopId(link, timetable_label)
            else:
                (first_stop_id, route, route_duration) = mhd_graph.createRouteIf(link, last_stop_id, timetable_label)
                if route:
                    conn_duration = conn_duration + route_duration
                    connection.addRoute(route)
                    if first_stop_id == self.endStop_:
                        break
                # last link
                if link == conn_path[-1]:
                    last_stop_id = self.endStop_
                else:
                    last_stop_id = mhd_graph.getStopId(link, timetable_label)
            
            try: 
                if first_stop_id == last_stop_id:
                    # TODO: fix this
                    print "redundant route indicator signalled"
                (route, route_duration) = mhd_graph.createRoute(link, first_stop_id, last_stop_id, timetable_label)
                connection.addRoute(route)
                conn_duration = conn_duration + route_duration
            except InvalidRoutePath:
                connection = None
                break
            
        if connection:
            connection.setDuration(conn_duration)
            if self.connections_.has_key(conn_duration):
                self.connections_[conn_duration].append(connection)
            else:
                self.connections_[conn_duration] = [connection]
                
            self.num_connections_ = self.num_connections_ + 1    


    def getConnections(self): 
        return self.connections_


    def getNumConnections(self): 
        return self.num_connections_ 



    def __str__(self):        
        #return "cur_stop: %d, num_xfer: %d, num_walking: %d, seen_links: %s, link_stops: %s, connections: %s" % (self.curStop_, self.num_xfer_, self.num_walking_, self.seen_links_, self.link_stops_, self.connections_)        
        return "cur_stop: %d, max_num_xfer: %d, num_xfer: %d, max_num_walking: %d, num_walking: %d, seen_links: %s" % (self.curStop_, self.max_num_xfer_, self.num_xfer_, self.max_num_walking_, self.num_walking_, self.seen_links_)
    
    def __unicode__(self):        
        #return "cur_stop: %d, num_xfer: %d, num_walking: %d, seen_links: %s, link_stops: %s, connections: %s" % (self.curStop_, self.num_xfer_, self.num_walking_, self.seen_links_, self.link_stops_, self.connections_)   
        return "cur_stop: %d, max_num_xfer: %d, num_xfer: %d, max_num_walking: %d, num_walking: %d, seen_links: %s" % (self.curStop_, self.max_num_xfer_, self.num_xfer_, self.max_num_walking_, self.num_walking_, self.seen_links_)


class MHD_LinkRepo:
    def __init__(self):
        self.linkRepo_ = {}
        if os.getcwd().find('/mhd') != -1:
            self.linkRepo_['wrk_days_school'] = pickle.load(open('../graphs/link_repo_workdays_school.pickle', 'r'))
            self.linkRepo_['wrk_days_noschool'] = pickle.load(open('../graphs/link_repo_workdays_noschool.pickle', 'r'))
            self.linkRepo_['weekend'] = pickle.load(open('../graphs/link_repo_weekend.pickle', 'r'))
        else:
            self.linkRepo_['wrk_days_school'] = pickle.load(open('graphs/link_repo_workdays_school.pickle', 'r'))
            self.linkRepo_['wrk_days_noschool'] = pickle.load(open('graphs/link_repo_workdays_noschool.pickle', 'r'))
            self.linkRepo_['weekend'] = pickle.load(open('graphs/link_repo_weekend.pickle', 'r'))

    
    def getXferLinks(self, link_t, timetable_label, ctx):
        xfer_links_repo = []
        last_stop = False
        link_name = link_t[0]
        dir = link_t[1]
        stop_num = link_t[2]
        
        # link must pass at least one stop before transferring
        cur_stop_num = stop_num + 1
        lr = self.linkRepo_[timetable_label]
        while not last_stop: 
            try:
                xfer_links_raw = lr[link_name][dir][cur_stop_num]['xfer_links'][:]
                
                for w_xfer_links_repo in lr[link_name][dir][cur_stop_num]['w_xfer_links']:
                    for w_xfer_link in w_xfer_links_repo['links']: 
                        xfer_links_raw.append((w_xfer_link['name'], w_xfer_link['dir'], w_xfer_link['stop_num']))

                xfer_links = deque()                        
                for xfer_link in xfer_links_raw:
                    if ctx.linkInEndStopLinks(xfer_link):
                        xfer_links.appendleft(xfer_link)
                    else:
                        xfer_links.append(xfer_link)
                
                xfer_links_repo.append({'stop_id': lr[link_name][dir][cur_stop_num]['stop_id'], 
                                        'stop_num': cur_stop_num,
                                        'xfer_links': list(xfer_links)
                                      })
                cur_stop_num = cur_stop_num + 1
            except KeyError:
                last_stop = True
        return xfer_links_repo
    
    
    def getStopId(self, link_t, timetable_label):
        lr = None 
        link_name = link_t[0]
        dir = link_t[1]
        stop_num = link_t[2]
        try:
            lr = self.linkRepo_[timetable_label]
            try:
                return lr[link_name][dir][stop_num]['stop_id']
            except KeyError:
                raise NoSuchStop
        except KeyError:
            raise NoSuchLinkRepo


class MHD_Graph:
    def __init__(self, linkRepo):
        self.mhdG_ = {}
        if os.getcwd().find('/mhd') != -1:        
            self.mhdG_['wrk_days_school'] = nx.read_gpickle('../graphs/mhdg_workdays_school.pickle')
            self.mhdG_['wrk_days_noschool'] = nx.read_gpickle('../graphs/mhdg_workdays_noschool.pickle')
            self.mhdG_['weekend'] = nx.read_gpickle('../graphs/mhdg_weekend.pickle')
            # mini graphs only for testing
            self.mhdG_['mini_onexfer_nowalking'] = nx.read_gpickle('../graphs/mhdg_mini_onexfer_nowalking.pickle')
            self.mhdG_['mini_twoxfer_nowalking'] = nx.read_gpickle('../graphs/mhdg_mini_twoxfer_nowalking.pickle')
            self.mhdG_['mini_threexfer_nowalking'] = nx.read_gpickle('../graphs/mhdg_mini_threexfer_nowalking.pickle')    
            self.mhdG_['mini_zeroxfer_walking'] = nx.read_gpickle('../graphs/mhdg_mini_zeroxfer_walking.pickle')
            self.mhdG_['mini_onexfer_walking'] = nx.read_gpickle('../graphs/mhdg_mini_onexfer_walking.pickle')
            self.mhdG_['mini_twoxfer_walking'] = nx.read_gpickle('../graphs/mhdg_mini_twoxfer_walking.pickle')
            self.mhdG_['mini_twoxfer_twowalking'] = nx.read_gpickle('../graphs/mhdg_mini_twoxfer_twowalking.pickle')                             
            self.mhdG_['mini_threexfer_walking'] = nx.read_gpickle('../graphs/mhdg_mini_threexfer_walking.pickle')
            self.mhdG_['mini_threexfer_twowalking'] = nx.read_gpickle('../graphs/mhdg_mini_threexfer_twowalking.pickle')            
            self.mhdG_['mini_threexfer_threewalking'] = nx.read_gpickle('../graphs/mhdg_mini_threexfer_threewalking.pickle')
            self.mhdG_['our_mini'] = nx.read_gpickle('../graphs/our_mini_graph.pickle')
        else:
            self.mhdG_['wrk_days_school'] = nx.read_gpickle('graphs/mhdg_workdays_school.pickle')
            self.mhdG_['wrk_days_noschool'] = nx.read_gpickle('graphs/mhdg_workdays_noschool.pickle')
            self.mhdG_['weekend'] = nx.read_gpickle('graphs/mhdg_weekend.pickle')         
            # mini graphs only for testing
            self.mhdG_['mini_onexfer_nowalking'] = nx.read_gpickle('graphs/mhdg_mini_onexfer_nowalking.pickle')
            self.mhdG_['mini_twoxfer_nowalking'] = nx.read_gpickle('graphs/mhdg_mini_twoxfer_nowalking.pickle')
            self.mhdG_['mini_threexfer_nowalking'] = nx.read_gpickle('graphs/mhdg_mini_threexfer_nowalking.pickle')  
            self.mhdG_['mini_onexfer_walking'] = nx.read_gpickle('graphs/mhdg_mini_onexfer_walking.pickle')                   
            self.mhdG_['mini_twoxfer_walking'] = nx.read_gpickle('graphs/mhdg_mini_twoxfer_walking.pickle')
            self.mhdG_['mini_twoxfer_twowalking'] = nx.read_gpickle('graphs/mhdg_mini_twoxfer_twowalking.pickle')
            self.mhdG_['mini_threexfer_walking'] = nx.read_gpickle('graphs/mhdg_mini_threexfer_walking.pickle')
            self.mhdG_['mini_threexfer_twowalking'] = nx.read_gpickle('graphs/mhdg_mini_threexfer_twowalking.pickle')
            self.mhdG_['mini_threexfer_threewalking'] = nx.read_gpickle('graphs/mhdg_mini_threexfer_threewalking.pickle')            
            self.mhdG_['our_mini'] = nx.read_gpickle('graphs/our_mini_graph.pickle')
        self.linkRepo_ = linkRepo
        

    def getConnections(self, a, b, a_departure, timetable_label, max_num_xfer = 3, max_num_connections = 5, debug = True):
        connections = []
           
        live_timetable_label = departure_to_timetable_label(a_departure)
        
        a_links = self.getLinks(a, timetable_label)
        b_links = self.getLinks(b, timetable_label)
        
        mhd_ctx = MHD_Context(a, b, max_num_xfer, 0, max_num_connections, a_links, b_links)
        for a_link in a_links:
            self.search(a_link, timetable_label, mhd_ctx)
            if mhd_ctx.getNumConnections() >= max_num_connections:
                break
            mhd_ctx.reset()      
                      
        all_connections = mhd_ctx.getConnections()
        if all_connections:
            durations = all_connections.keys()
            durations.sort()
            c = 0
            for duration in durations:
                for connection in all_connections[duration]:
                    if c == max_num_connections:
                        break  
                    stop = a
                    conn_duration = 0
                    validConnection = True
                    departure = a_departure
                    for route in connection.getRoutes():
                        if route.isWalking():
                            arrival = departure
                            waiting = 0
                        else:
                            try:
                                (arrival, waiting) = route.getLink().getNextArrival(stop, route.getLinkDirection(), live_timetable_label, departure)
                            except NoSuchLinkStop:
                                validConnection = False
                                break
                            except InvalidArrival:
                                validConnection = False
                                break
                        route.setFirstStopArrival(arrival)
                        route_duration = route.getDuration()
                        conn_duration = conn_duration + waiting + route_duration
                        if conn_duration > MAX_ALLOWED_CONNECTION_DURATION_MIN:
                            validConnection = False
                            break
                        departure = datetime.datetime(departure.year, departure.month, departure.day, arrival.hour, arrival.minute) + datetime.timedelta(minutes = route_duration)
                        stop = route.getLastStopId()
    
                    if validConnection:
                        connection.setDuration(conn_duration)
                        connections.append(connection)
                        c = c + 1
                
                if c  == max_num_connections:
                    break
        
        if debug:
            dumpConnections(a, b, connections, a_departure)
                
        return connections



    def getConnections__test(self, a, b, a_departure, max_num_xfer = 3, max_num_walking = 3, max_num_connections = 5, timetable_label = None, debug = True):
        connections = []
           
        if not timetable_label:
            timetable_label = departure_to_timetable_label(a_departure)    
        live_timetable_label = departure_to_timetable_label(a_departure)
        
        a_links = self.getLinks(a, timetable_label)
        b_links = self.getLinks(b, timetable_label)
        num_xfer = 0
        all_connections = {}
        
        while not num_xfer > max_num_xfer:
            mhd_ctx = MHD_Context(a, b, num_xfer, max_num_walking, max_num_connections, a_links, b_links)
            for a_link in a_links:
                self.search(a_link, timetable_label, mhd_ctx)
                if mhd_ctx.getNumConnections() >= max_num_connections:
                    break
                mhd_ctx.reset()      
                mhd_ctx.setNumXfer(num_xfer)
                          
            all_connections = mhd_ctx.getConnections()
            if all_connections:
                durations = all_connections.keys()
                durations.sort()
                c = 0
                for duration in durations:
                    for connection in all_connections[duration]:
                        if c == max_num_connections:
                            break  
                        stop = a
                        conn_duration = 0
                        validConnection = True
                        departure = a_departure
                        for route in connection.getRoutes():
                            if route.isWalking():
                                arrival = departure
                                waiting = 0
                            else:
                                try:
                                    (arrival, waiting) = route.getLink().getNextArrival(stop, live_timetable_label, departure)
                                except NoSuchLinkStop:
                                    validConnection = False
                                    break
                                except InvalidArrival:
                                    validConnection = False
                                    break
                            route.setFirstStopArrival(arrival)
                            route_duration = route.getDuration()
                            conn_duration = conn_duration + waiting + route_duration
                            if conn_duration > MAX_ALLOWED_CONNECTION_DURATION_MIN:
                                validConnection = False
                                break
                            departure = datetime.datetime(departure.year, departure.month, departure.day, arrival.hour, arrival.minute) + datetime.timedelta(minutes = route_duration)
                            stop = route.getLastStopId()
        
                        if validConnection:
                            connection.setDuration(conn_duration)
                            connections.append(connection)
                            c = c + 1
                    
                    if c  == max_num_connections:
                        break

                if c > 0:   # while                
                    break
            
            num_xfer = num_xfer + 1
        
        if debug:
            dumpConnections(a, b, connections, a_departure)
                
        return connections
    
    
            
    def search(self, cur_link, timetable_label, ctx, debug = False):
        cur_link = cur_link
        cur_stop = ctx.getCurrentStop()
        num_xfer = ctx.getNumXfer()
        stop_num = None
                                                                       
        if ctx.linkInEndStopLinks(cur_link):
            ctx.onEndStop(cur_link, self, timetable_label)
            return ctx.getConnections()
                                        
        for xfer_links_repo in self.getXferLinks(cur_link, timetable_label, ctx):
            
            #if cur_link[:2] == ('21', 53):
            #    print xfer_links_repo['stop_num']
            
            stop_num = xfer_links_repo['stop_num'];
            
            for xfer_link in xfer_links_repo['xfer_links']:
                
                if cur_link[:2] == ('21', 53) and xfer_links_repo['stop_num'] == 14 and xfer_link[:2] == (u'8', 12):
                #if cur_link[:2] == ('21', 53) and xfer_links_repo['stop_num'] == 14:
                    #print xfer_link
                    pass
                
                #ctx.addLinkStop(xfer_link, cur_link, xfer_links_repo['stop_num']);
                                                                                      
                if num_xfer > 0:
                    ctx.setNumXfer(num_xfer - 1)
                    ctx.setCurrentStop(self.getStopId(xfer_link, timetable_label))
                    self.search(xfer_link, timetable_label, ctx, debug)
                else:
                    ctx.setNumXfer(num_xfer + 1)
                    break
                    
        return ctx.getConnections()
                    
                    
                    
    def getXferLinks(self, link_t, timetable_label, ctx):
        return self.linkRepo_.getXferLinks(link_t, timetable_label, ctx)
        

    def getStopId(self, link_t, timetable_label):
        return self.linkRepo_.getStopId(link_t, timetable_label)


    def createRouteIf(self, link_t, stop_id, timetable_label):
        rv = None
        stop = self.getStop(stop_id, timetable_label)
        for l in stop['links']:
            if l['name'] == link_t[0] and l['dir'] == link_t[1]:
                rv = (stop_id, None, 0)
                break
        # link does not stop at stop_id, need to create a walking route
        if not rv:
            for edge in self.getEdges(stop_id, timetable_label):
                if edge[3]['type'] == 'w':
                    nearby_stop = self.getStop(edge[1], timetable_label)
                    for l in nearby_stop['links']:
                        if l['name'] == link_t[0] and l['dir'] == link_t[1]:
                            rv = (edge[1], Route('w', None, [stop, nearby_stop], int(edge[3]['weight'])), int(edge[3]['weight']))
                            break
                if rv:
                    break
        return rv
                    


    def createRoute(self, link_t, first_stop_id, last_stop_id, timetable_label):
        endRoute = False
        duration = 0
        node = first_stop_id
        stops = []
        
        while not endRoute:
            linkEdge = False
            for edge in self.getEdges(node, timetable_label):
                if edge[2] == link_t[0] and edge[3]['type'] == 'd' and edge[3]['dir'] == link_t[1]:
                    stop = self.getStop(edge[0], timetable_label)
                    stops.append(stop)
                    duration = duration + edge[3]['weight']                            
                    node = edge[1]
                    linkEdge = True
                    if stop['id'] == last_stop_id:
                        endRoute = True
                    else:
                        for l in stop['links']:
                            if l['name'] == link_t[0] and l['dir'] == link_t[1]:
                                if l['last']:
                                    raise EndStopReached  
                                else:
                                    break                              
                    break
                                
            if not linkEdge:
                raise InvalidRoutePath
        
        return (Route(link_t[0], link_t[1], stops, duration), duration)




    def getLinks__old(self, node, timetable_label):
        links = []
        try:
            for e in self.mhdG_[timetable_label].edges_iter(node, keys = True, data = True):
                if e[2] != 0:                    
                    links.append(e[2])
            return links
        except KeyError:
            raise NoSuchStop


    def getLinks(self, stop_id, timetable_label):
        links = []
        try:
            for link in self.mhdG_[timetable_label].node[stop_id]['links']:
                links.append((link['name'], link['dir'], link['stop_num']))
            return links
        except KeyError:
            raise NoSuchStop
        
            
    def getStop(self, stopId, timetable_label):
        try:            
            return self.mhdG_[timetable_label].node[stopId]
        except KeyError:
            raise NoSuchStop


    def getEdges(self, node, timetable_label):
        return self.mhdG_[timetable_label].edges_iter(node, data = True, keys = True)        

mhd_graph = MHD_Graph(MHD_LinkRepo())


class JourneyPlanner:
    def __init__(self):
        global mhd_graph
        self.mhdG_ = mhd_graph 
        self.stopLocator_ = MHD_StopLocator()
        


    def getPlan_test(self, start, end, departure, max_num_xfer = 3, max_num_connections = 3):
        # direct connection
        connections = self.mhdG_.getConnections(30, 32, departure, max_num_xfer = 0, max_num_walking = 0, max_num_connections = max_num_connections)
        connections = self.mhdG_.getConnections(470, 385, departure, max_num_xfer = 0, max_num_walking = 0, max_num_connections = max_num_connections)
        #connections = self.mhdG_.getConnections(1, 3, departure, max_num_xfer, max_num_connections, 'mini_onexfer_nowalking')
        
        # 1 xfer, no walking
        connections = self.mhdG_.getConnections(472, 384, departure, max_num_xfer = 1, max_num_walking = 0, max_num_connections = max_num_connections)
        #connections = self.mhdG_.getConnections(1, 7, departure, max_num_xfer = 1, max_num_walking = 0, max_num_connections = max_num_connections, timetable_label = 'mini_onexfer_nowalking')
        
        # 1 xfer, with walking
        connections = self.mhdG_.getConnections(30, 384, departure, max_num_xfer = 1, max_num_walking = 1, max_num_connections = max_num_connections)

        # 2 xfer, no walking
        #connections = self.mhdG_.getConnections(1, 19, departure, max_num_xfer = 2, max_num_walking = 1, max_num_connections = max_num_connections, timetable_label = 'mini_twoxfer_nowalking')

        # 2 xfer, walking
        connections = self.mhdG_.getConnections(115, 1141, departure, max_num_xfer = 6, max_num_walking = 1, max_num_connections = max_num_connections)
        #connections = self.mhdG_.getConnections(115, 1141, departure, max_num_xfer = 2, max_num_walking = 1, max_num_connections = max_num_connections)

        # 3 xfer, no walking
        #connections = self.mhdG_.getConnections(1, 25, departure, max_num_xfer, max_num_connections, 'mini_threexfer_nowalking')


        # direct connection, walking
        #connections = self.mhdG_.getConnections(1, 19, departure, max_num_xfer, max_num_connections, 'mini_zeroxfer_walking')

        # 1 xfer, walking
        #connections = self.mhdG_.getConnections(1, 22, departure, max_num_xfer, max_num_connections, 'mini_onexfer_walking')

        # 2 xfer, walking
        #connections = self.mhdG_.getConnections(1, 26, departure, max_num_xfer = 2, max_num_walking = 1, max_num_connections = max_num_connections, timetable_label = 'mini_twoxfer_walking')

        # 2 xfer, 2 walking
        #connections = self.mhdG_.getConnections(1, 22, departure, max_num_xfer = 2, max_num_walking = 1, max_num_connections = max_num_connections, timetable_label = 'mini_twoxfer_twowalking')

        # 3 xfer, walking
        #connections = self.mhdG_.getConnections(1, 29, departure, max_num_xfer, max_num_connections, 'mini_threexfer_walking')

        # 3 xfer, 2 walking
        #connections = self.mhdG_.getConnections(1, 30, departure, max_num_xfer, 'mini_threexfer_twowalking')

        # 3 xfer, 3 walking
        #connections = self.mhdG_.getConnections(1, 31, departure, max_num_xfer, 1, 'mini_threexfer_threewalking')

        # no connection
        #connections = self.mhdG_.getConnections(31, 1, departure, max_num_xfer, max_num_connections, 'mini_threexfer_threewalking')

        # no walking from stop 
        #connections = self.mhdG_.getConnections(1, 32, departure, max_num_xfer, max_num_connections, 'mini_threexfer_threewalking')
                
        return connections



    def getPlan(self, start, end, departure, debug = False):        
        nearByStopsStart = self.stopLocator_.find_nearby_stops_by_latlng(start.getLat(), start.getLng())
        nearByStopsEnd = self.stopLocator_.find_nearby_stops_by_latlng(end.getLat(), end.getLng())
        seenPaths = []
        connections = []
        gotEnoughConnections = False
        tl = departure_to_timetable_label(departure)

        num_xfer = 0
        while not num_xfer > MAX_ALLOWED_NUM_XFER:                    

            if num_xfer > 1 and connections:
                break
            
            for endStop in nearByStopsEnd:
                for startStop in nearByStopsStart:
                    if startStop[0].name != endStop[0].name:  
                        for connection in self.mhdG_.getConnections(startStop[0].id, endStop[0].id, departure, tl, num_xfer, MAX_NUM_CONNECTIONS, debug):
#                            path = connection.getPath()
#                            if not path in seenPaths:
#                                if len(connections) < MAX_NUM_CONNECTIONS:
#                                    connection.setStartStop(startStop[0])
#                                    connection.setEndStop(endStop[0])
#                                    connections.append(connection)
#                                    seenPaths.append(path)

                            connection.setStartStop(startStop[0])
                            connection.setEndStop(endStop[0])
                            connections.append(connection)
                                                                        
#                        if num_xfer < 2 and len(connections) == MAX_NUM_CONNECTIONS:
#                            gotEnoughConnections = True
#                            break
                                                
                if gotEnoughConnections:
                    break
            if gotEnoughConnections:
                break
                       
            num_xfer = num_xfer + 1

        connections.sort(key = lambda x: x.getDuration())

        if debug:
            for connection in connections:
                print "%s -> %s, %d min" % (connection.getStartStopName().encode('utf-8'), connection.getEndStopName().encode('utf-8'), connection.getDuration())
                print "%s\n" % connection     
                           
        return connections       
        

def main():
    start_tm = datetime.datetime.now()

    departure = datetime.datetime.strptime('19.10.2011 11:00', '%d.%m.%Y %H:%M')
    jp = JourneyPlanner()
    # 48.194829, 17.0310596 - pri krizi
    # 48.1883002, 17.0326091 - peknikova
#    i = 1
#    for connection in jp.getPlan(LatLng(48.194829, 17.0310596), LatLng(48.1883002, 17.0326091), departure):
#        print 'Connection %d:\n%s\n' % (i, connection)
#        i = i + 1


    # 48.194829, 17.0310596 - pri krizi
    # 48.1650, 17.1245 - ovrucska 
    connections = jp.getPlan(LatLng(48.194829, 17.0310596), LatLng(48.1650, 17.1245), departure, False)

    end_tm = datetime.datetime.now()

    print "runtime: %s" % (end_tm - start_tm)
    
#    start_tm = datetime.datetime.now()
#    end_tm = datetime.datetime.now()

if __name__ == '__main__':
    main()
